# 随机访问
数组是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据
正是因为连续的内存空间和相同类型的数据这两个限制，数组拥有了随机访问的特性
线性表，即数据之间是简单的前后关系，其他线性表还有: 链表，队列，栈等
# 低效的插入和删除
但是同样是因为上述限制，数组的插入和删除两个操作，效率非常低下，时间复杂度:
- 最好:
O(1) - 最坏:
O(n) - 平均:
O((1+2+...+n)/n) = O(n)
提高效率的办法
- 对于插入操作，如果数组本身顺序不重要，则可以通过交换，降低时间复杂度至
O(1) - 对于删除操作，每次删除元素时，可以暂时先保留数据，直到数组空间不足，再统一删除
- JVM 标记清除垃圾回收算法的核心思想
# 容器与数组
大多数编程语言都提供容器类，如ArrayList, vector等，这些容器类封装了数组的操作细节(如数据的搬迁工作)，方便用户使用，同时也提供了数组的动态扩容
动态扩容涉及内存开辟和数据搬迁，较为耗时，因此如果可以，应当事先指定合适的容器大小
什么时候数组比容器类更适合
- 对于Java，
ArrayList无法存储基本数据类型，需要借助自动装箱开箱，会有一定性能损耗 - 数据大小已知，数组操作简单
大多数情况，如果不是需要将性能优化做到极限，可以直接使用容器类
链表 →